[最小生成树] leetcode 1135 Connecting Cities With Minimum Cost |
您所在的位置：网站首页 › leetcode 1135 › [最小生成树] leetcode 1135 Connecting Cities With Minimum Cost |
|
problem: https://leetcode.com/contest/biweekly-contest-5/problems/connecting-cities-with-minimum-cost/ 双周赛题目。此题就是没有什么变化的最小生成树，以下给出两种经典解法：
(1).并查集 首先假设所有的顶点都是一棵单独的树，之后依次选择权重最小的边，使得它连接两棵不同的树，并将两棵树合并为一棵树。当选择了N - 1条边（只剩下一棵树）的时候，意味着得到了最小生成树。 struct edge { int vertex1; int vertex2; int value; edge(int v1, int v2, int val) :vertex1(v1), vertex2(v2), value(val) { } friend bool operator e2.value; } }; class Solution { public: vector nums; int Find(int x) { while(x != nums[x]) { x = nums[x]; } return x; } void Union(int x, int y) { int px = Find(x); int py = Find(y); if(px != py) { nums[px] = py; } } bool InSameSet(int x,int y) { int px = Find(x); int py = Find(y); return px == py; } int minimumCost(int N, vector& conections) { priority_queue pq; nums.resize(N + 1); for(int i = 1; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |